#include <iostream>
#include <vector>
#include <algorithm>

const int MOD = 1e9 + 7;

class Union {
public:
    std::vector<int> pt, rk;

    Union(int n) : pt(n), rk(n, 0) {
        for (int i = 0; i < n; ++i) {
            pt[i] = i;
        }
    }

    int find(int x) {
        if (pt[x] != x) {
            pt[x] = find(pt[x]);
        }
        return pt[x];
    }

    bool merge(int x, int y) {
        int rx = find(x);
        int ry = find(y);
        if (rx != ry) {
            if (rk[rx] > rk[ry]) {
                pt[ry] = rx;
            } else if (rk[rx] < rk[ry]) {
                pt[rx] = ry;
            } else {
                pt[ry] = rx;
                ++rk[rx];
            }
            return true;
        }
        return false;
    }
};

bool isTree(int n, const std::vector<std::pair<int, int>>& egs) {
    if (egs.size() != n - 1) return false;

    Union uf(n);
    for (const auto& edge : egs) {
        if (!uf.merge(edge.first, edge.second)) {
            return false; 
        }
    }

    int root = uf.find(0);
    for (int i = 1; i < n; ++i) {
        if (uf.find(i) != root) return false;
    }

    return true;
}

int cnt_tree(int n, int p, int tp) {
    std::vector<std::pair<int, int>> egs;
    
    for (int i = 0; i < n - 1; ++i) {
        egs.emplace_back(i, i + 1);
    }

    if (tp == 2) {
        egs.emplace_back(n - 2, 0); 
    }

    for (int i = 0; i < n - 1; ++i) {
        if (i % p == 0) {
            egs.emplace_back(i, n - 1);
        }
    }

    int cnt = 0;
    for (int msk = 0; msk < (1 << egs.size()); ++msk) {
        std::vector<std::pair<int, int>> sg;
        for (size_t i = 0; i < egs.size(); ++i) {
            if (msk & (1 << i)) {
                sg.push_back(egs[i]);
            }
        }

        if ((int)sg.size() == n - 1 && isTree(n, sg)) {
            cnt = (cnt + 1) % MOD;
        }
    }

    return cnt;
}

int main() {
    int t, tp;
    std::cin >> t >> tp;

    while (t--) {
        int n, p;
        std::cin >> n >> p;
        std::cout << cnt_tree(n, p, tp) << std::endl;
    }

    return 0;
}
